package algorithms.sort;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 选择排序<br>
 *
 * <br>算法思想：<br>
 * 1 找到数组中最小的那个元素<br>
 * 2 将它和数组到第一个元素交换位置<br>
 * 3 在剩下的元素中找到最小的，将它与数组的第二个元素交换<br>
 * 4 如此反复，直到将整个数组排序<br>
 *
 * <br>特点：<br>
 * 1 运行时间与输入无关<br>
 * 2 数组移动是最少的
 *
 */
public class SelectionSort {

	public static void sort(Comparable[] a){
		int N = a.length;
		for(int i = 0; i < N; i++){
			int min = i;
			for(int j = i + 1; j < N; j++){
				if(less(a[j], a[min]))
					min = j;
			}
			exch(a, i, min);
		}
	}
	
	private static boolean less(Comparable v, Comparable w){
		return v.compareTo(w) < 0;
	}
	
	private static void exch(Comparable[] a, int i, int j){
		Comparable t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
	
	public static void show(Comparable[] a){
		for(int i = 0; i < a.length; i++){
			System.out.print(a[i] + " ");
		}
		System.out.println();
	}
	
	
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			String s = br.readLine();
			String[] in = s.split(" ");
			SelectionSort.sort(in);
			SelectionSort.show(in);
		} catch (IOException e) {
			e.printStackTrace();
		}


	}

}
